public class tree {
    class treeNode{
        public int val;
        public treeNode left;
        public treeNode right;

        public treeNode(int val) {
            this.val = val;
        }
    }
    public  treeNode root;
    //插入
    public void insert(int key){
        if (root == null){
            root = new treeNode(key);
            return;
        }
        treeNode cur = root;
        treeNode parent = null;
        treeNode newRoot = new treeNode(key);

        while (cur != null){
            if (cur.val > key){
                parent = cur;
                cur = cur.left;
            } else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                return;
            }
        }
        if (parent.val > key){
            parent.left = newRoot;
        }else {
            parent.right = newRoot;
        }

    }
    //搜索
    public treeNode search(int key,treeNode root) {
        treeNode cur = root;
        if (root == null) {
            return null;
        }
        if (cur.val == key) {
            return cur;
        } else if (cur.val > key) {
            return search(key, cur.left);
        } else {
            return search(key, cur.right);
        }
    }
    //删除
    public void removeNode(int key) {
        treeNode cur = root;
        treeNode parent = null;
        //找节点
        while (cur != null){
            if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                //删除
                remove(parent,cur);
                return ;
            }
        }
    }

   private void remove(treeNode parent ,treeNode child){
            if (child.left == null){
                if (child == root){
                    root = child.right;
                } else if (child == parent.left) {
                    parent.left = child.right;
                }else {
                    parent.right = child.right;
                }
            } else if (child.right == null) {
                if (child == root){
                    root = child.left;
                } else if (child == parent.left) {
                    parent.left = child.left;
                }else {
                    parent.right = child.left;
                }
                //替换删除
            }else{
                treeNode t = child.left;
                treeNode tp = child;
                //找右边最小值
                while (t != null ){
                    tp = t;
                    t = t.left;
                }
                //第一种情况
                if(tp.left == t){
                    child.val = t.val;
                    tp.right = t.right;
                //第二种情况
                }else{
                    child.val = t.val;
                    tp.left = t.right;
                }
            }
        }

}
